use rand::Rng;

pub fn find_max_prime_factor(number: u128) -> u128 {
    let mut max_factor = 1u128;
    fac(number, &mut max_factor);
    max_factor
}
fn gcd(a: u128, b: u128) -> u128 {
    if b == 0 {
        return a;
    }
    gcd(b, a % b)
}

fn modular_mul(mut a: u128, mut b: u128, modulus: u128) -> u128 {
    let mut result = 0u128;
    a %= modulus;
    b %= modulus;
    while b > 0 {
        if b & 1 == 1 {
            result = (result + a) % modulus;
        }
        a = (a << 1) % modulus;
        b >>= 1;
    }
    result
}

fn modular_pow(mut base: u128, mut exponent: u128, modulus: u128) -> u128 {
    let mut result = 1u128;
    base %= modulus;
    while exponent > 0 {
        if exponent & 1 == 1 {
            result = modular_mul(result, base, modulus);
        }
        base = modular_mul(base, base, modulus);
        exponent >>= 1;
    }
    result
}
fn mr(x:u128,b: u128)->bool{
    let mut k:u128=x-1;
    while k!=0 {
        let  cur=modular_pow(b, k, x);
        if cur!=1&&cur!=x-1 {
            return false;
        }
        if (k&1)==1||cur==x-1 {
            return true;
        }
        k=k>>1;
    }
    return true;
}

fn is_prime(x: u128) -> bool {
    if x == 46_856_248_255_981 || x < 2 {
        return false;
    }
    if x == 2 || x == 3 || x == 7 || x == 61 || x == 24_251 {
        return true;
    }
    mr(x, 2) && mr(x, 61)
}

fn f(x: u128, c: u128, n: u128) -> u128 {
    (modular_mul(x, x, n) + c) % n
}

fn pr(n: u128) -> u128 {
    let mut rng = rand::thread_rng();
    let mut t = 0u128;
    let c = rng.gen_range(1..n);
    let mut stp = 0;
    let mut goal = 1u128;
    loop {
        goal <<= 1;
        let s = t;
        let mut val = 1u128;
        for _ in 1..=goal {
            t = f(t, c, n);
            let diff = if t > s { t - s } else { s - t };
            val = modular_mul(val, diff, n);
            stp += 1;
            if stp % 127 == 0 {
                let d = gcd(val, n);
                if d > 1 && d < n {
                    return d;
                }
            }
        }
        let d = gcd(val, n);
        if d > 1 && d < n {
            return d;
        }
    }
}

fn fac(n: u128, max_factor: &mut u128) {
    let mut stack = vec![n];
    while let Some(x) = stack.pop() {
        if x <= *max_factor || x < 2 {
            continue;
        }
        if is_prime(x) {
            if x > *max_factor {
                *max_factor = x;
            }
            continue;
        }
        let mut p = x;
        while p >= x || p == 1 {
            p = pr(x);
        }
        stack.push(p);
        stack.push(x / p);
    }
}